import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.concurrent.Semaphore;

/*
题目描述：实现两个函数用来序列化和反序列化二叉树
 */
public class E37 {
    public static void main(String[] args) {
        TreeNode1 root = new TreeNode1(1);
        root.left = new TreeNode1(2);
        root.right = new TreeNode1(3);
        root.left.left = new TreeNode1(4);
        root.left.right = new TreeNode1(5);
        root.right.left = new TreeNode1(6);
        root.right.right = new TreeNode1(7);

        String list = Serialize(root);

        System.out.println(list);

        TreeNode1 head = Deserialize(list);

        PrintTree(head);
    }
    public static String Serialize(TreeNode1 root) {
        StringBuilder sb = new StringBuilder();
        if(root == null){
            sb.append("#,");
            return sb.toString();
        }
        sb.append(root.val + ",");
        sb.append(Serialize(root.left));
        sb.append(Serialize(root.right));
        return sb.toString();
    }
    public static int index = -1;
    public static TreeNode1 Deserialize(String str) {
        index ++;
        if(index >= str.length()){
            return null;
        }
        String[] strr = str.split(",");
        TreeNode1 node = null;
        if(!strr[index].equals("#")){
            node = new TreeNode1(Integer.valueOf(strr[index]));
            node.left = Deserialize(str);
            node.right = Deserialize(str);
        }
        return node;
    }

    public static void PrintTree(TreeNode1 head){
        if(head == null){
            return;
        }
        Queue<TreeNode1> queue = new LinkedList<>();
        queue.add(head);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size; i++){
                TreeNode1 cur = queue.poll();
                System.out.print(cur.val + " ");
                if(cur.left != null){
                    queue.add(cur.left);
                }
                if(cur.right != null){
                    queue.add(cur.right);
                }
            }
        }
    }
}
